
public class Leetcode540 {

    public static void main(String[] args) {
        System.out.println(singleNonDuplicate(new int[]{3, 3, 7, 7, 11, 11, 12}));
    }

    /**
     * 全异或
     */
//    public static int singleNonDuplicate(int[] nums) {
//        int res = 0;
//        for (int num : nums) {
//            res ^= num;
//        }
//
//        return res;
//    }

    /**
     * 二分
     */
    public static int singleNonDuplicate(int[] nums) {
        int l = 0;
        int r = nums.length - 1;
        while (l < r) {
            int m = (r - l) / 2 + l;
            m -= m & 1;
            if (nums[m] == nums[m + 1]) {
                l = m + 2;
            } else {
                r = m;
            }
        }

        return nums[l];
    }
}
